# 二分查找非迭代
def binary(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1


# 二分查找迭代
def binary_recursion(arr, low, high, target):
    if low > high:
        return -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binary_recursion(arr, low, mid - 1, target)
        else:
            return binary_recursion(arr, mid + 1, high, target)


if __name__ == '__main__':
    # 二分查找非递归
    array = [2, 3, 5, 12, 22, 34, 35, 67]
    print(binary(array, 121))
    # 二分查找递归
    array = [2, 3, 5, 12, 22, 34, 35, 67]
    print(binary_recursion(array, 0, len(array) - 1, 121))
